from typing import *
from math import inf


class Solution:

    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
        n = len(nums1) + 1
        f = [[0] * n for _ in range(n)]
        idx = list(range(n - 1))
        print(idx)
        idx.sort(key=lambda a: nums2[a])
        for i in range(1, n):
            for j in range(1, n):
                f[j][i] = max(
                    f[j - 1][i],
                    f[j - 1][i - 1] + nums1[idx[j - 1]] + nums2[idx[j - 1]] * i)
        for i in f:
            print(i)
        s1, s2 = sum(nums1), sum(nums2)
        # print(s1,s2)
        for i in range(n):
            c = s1 + s2 * i - f[n - 1][i]
            if c <= x:
                return i
        return -1


s = Solution()
# print(s.minimumTime([7, 9, 8, 5, 8, 3], [0, 1, 4, 2, 3, 1], 37))
print(s.minimumTime([4, 4, 9, 10], [4, 4, 1, 3], 16))
print(s.minimumTime([4, 4, 9, 10], [4, 4, 1, 3], 17))

[1, 2, 3]
[1, 2, 3]
4
[1, 2, 3]
[3, 3, 3]
4
[1, 2, 3]
[3, 3, 3]
6
[4, 4, 9, 10]
[4, 4, 1, 3]
16
[7, 9, 8, 5, 8, 3]
[0, 1, 4, 2, 3, 1]
37